|
|
Konvexně nezávislé podmnožiny konečných množin bodů
Zajíc, Vítězslav ; Valtr, Pavel (vedoucí práce) ; Cibulka, Josef (oponent)
Nech' fd(n), pro n > d ≥ 2, je nejmenší přirozené číslo takové, že každá množina fd(n) bod· v obecné poloze v Rd obsahuje n bod· v konvexní poloze. Nech' hd(n, k), pro n > d ≥ 2 a k ≥ 0, je nejmenší přirozené číslo takové, že v každé množině hd(n, k) bod· v obecné poloze v Rd existuje n bod· v konvexní poloze, uvnitř jejichž konvexního obalu je nejvýše k dalších bod·. Valtr ukázal, že h4(n, 0) neexistuje pro žádné n ≥ 249. V této práce předvedeme, že h4(n, 0) neexistuje pro žádné n ≥ 137. Ukážeme, že h3(8, k) ≤ f3(8) pro všechna k ≥ 26, h4(10, k) ≤ f4(10) pro všechna k ≥ 147 a h5(12, k) ≤ f5(12) pro všechna k ≥ 999. Dále nech' fd(k, n) je nejmenší číslo takové, že v každé množině fd(k, n) bod· v obecné poloze v Rd existuje n bod· jejichž konvexní obal má alespoň k vrchol·. Ukážeme, že pro n ≥ k ≥ d + 1, d ≥ 2, fd(k, n) ≥ (n − 1) (k − 1)/(cd logd−2 (n − 1)) , kde cd je konstanta závislá pouze na d.
|
|
|
Odhady počtu prázdných čtyřstěnů a ostatních simplexů
Reichel, Tomáš ; Valtr, Pavel (vedoucí práce) ; Balko, Martin (oponent)
Mějme v jednotkové krychli konečnou množinu M uniformně náhodně zvolených bodů. Každá čtveřice bodů z M má jakožto čtyřstěn buď uvnitř nějaký bod z množiny M, nebo je prázdná. V této práci předvedeme horní odhad střední hodnoty počtu těchto prázdných čtyřstěnů vzhledem k velikosti množiny M a ukážeme, jak je odhad nejspíše vzdálen od aproximace střední hodnoty, kterou necháme přímočarým algoritmem spočí- tat počítač. Nakonec pak opustíme trojrozměrný případ a budeme se věnovat obecnější úloze v libovolné dimenzi d, kde namísto prázdných čtyřstěnů v krychli budou figurovat prázdné d-simplexy v d-dimenzionální krychli. Horní odhad pro d-dimenzionální případ pak porovnáme s výsledky z jiného článku o stejném tématu. 1
|
|
|
Konvexně nezávislé podmnožiny konečných množin bodů
Zajíc, Vítězslav ; Valtr, Pavel (vedoucí práce) ; Cibulka, Josef (oponent)
Nech' fd(n), pro n > d ≥ 2, je nejmenší přirozené číslo takové, že každá množina fd(n) bod· v obecné poloze v Rd obsahuje n bod· v konvexní poloze. Nech' hd(n, k), pro n > d ≥ 2 a k ≥ 0, je nejmenší přirozené číslo takové, že v každé množině hd(n, k) bod· v obecné poloze v Rd existuje n bod· v konvexní poloze, uvnitř jejichž konvexního obalu je nejvýše k dalších bod·. Valtr ukázal, že h4(n, 0) neexistuje pro žádné n ≥ 249. V této práce předvedeme, že h4(n, 0) neexistuje pro žádné n ≥ 137. Ukážeme, že h3(8, k) ≤ f3(8) pro všechna k ≥ 26, h4(10, k) ≤ f4(10) pro všechna k ≥ 147 a h5(12, k) ≤ f5(12) pro všechna k ≥ 999. Dále nech' fd(k, n) je nejmenší číslo takové, že v každé množině fd(k, n) bod· v obecné poloze v Rd existuje n bod· jejichž konvexní obal má alespoň k vrchol·. Ukážeme, že pro n ≥ k ≥ d + 1, d ≥ 2, fd(k, n) ≥ (n − 1) (k − 1)/(cd logd−2 (n − 1)) , kde cd je konstanta závislá pouze na d.
|
|
| |
host ::
RSS.